class Solution {
    /*
        思路：二分，时间O(logN)
        对于例子: nums = [1,3,4,2,2]
        count表示nums中小于等于num的数有多少个

        num:   1 2 3 4
        count: 1 3 4 5
        bool:  0 1 1 1

        易知 bool 单调有序 可用二分求解
            
    */
    public int findDuplicate(int[] nums) {
        int left = 1, right = nums.length - 1;
        int ans = -1;
        while (left <= right) {
            int mid = (left + right) >> 1;

            int cnt = 0;
            for (int num : nums) {
                if (num <= mid) cnt++;
            }

            if (cnt <= mid) {
                left = mid + 1;
            } else {
                ans = mid;
                right = mid - 1;
            }
        }

        return ans;
    }
}

class Solution {
    /**
        思路: 快慢指针环形链表解法
     */
    public int findDuplicate(int[] nums) {
        int low = 0, fast = 0;
        while(true){
            low = nums[low];
            fast = nums[nums[fast]];
            if(low==fast)
                break;
        }

        // 交点为fast,low移动到起点
        low = 0;
        while(low!=fast){
            low = nums[low];
            fast = nums[fast];
        }
        
        return low;
    }
}

/**
 0 1
 1 1
0->1->1

环:1
 index: 0,1,2,3,4
  nums:[1,3,4,2,2]
  link: 0->1->3->2->4
                 |--|

环2:
 index: 0,1,2,3,4 
  nums:[3,1,3,4,2]
  link: 0->3->4->2
           |-----|

正常情况:
 index: 0,1,2,3,4 
  nums:[1,2,3,4,5]
  link: 0->1->2->3->4->5

 */